Questions and answers -- a category arising in linear logic, complexity theory, and set theory

摘要

A category used by de Paiva to model linear logic also occurs in Vojtas'sanalysis of cardinal characteristics of the continuum. Its morphisms have beenused in describing reductions between search problems in complexity theory. Wedescribe this category and how it arises in these various contexts. We alsoshow how these contexts suggest certain new multiplicative connectives forlinear logic. Perhaps the most interesting of these is a sequential compositionsuggested by the set-theoretic application.